package graphic;

/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 * 示例:
 *
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true.
 * 给定 word = "SEE", 返回 true.
 * 给定 word = "ABCB", 返回 false.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class WordExist {

    int[][] region = new int[][]{{ -1, 0 }, {1,0},{0,-1},{0,1}};
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0){
            return false;
        }
        if(word == null || word.length() == 0){
            return false;
        }

        boolean[][] used = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length; i ++) {
            for(int j = 0; j < board[0].length; j ++) {
                if(isFound(board, word, 0, i, j, used)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean isFound(char[][] board, String word, int index, int i, int j, boolean[][] used){

        if(i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1 || used[i][j]){
            return false;
        }
        if(index == word.length() - 1 && board[i][j] == word.charAt(index)){
            return true;
        }
        if(board[i][j] == word.charAt(index)) {
            used[i][j] = true;
            for(int k = 0; k < 4; k ++){
                if(isFound(board, word, index + 1, i + region[k][0], j + region[k][1], used)){
                    return true;
                }
            }
            used[i][j] = false;
        }
        return false;
    }

    public static void main(String[] args){
        System.out.println((new WordExist()).exist(new char[][]{{'a', 'a'}}, "aa"));
    }
}
